﻿/*============================================
 * 类名 :Identify
 * 描述 :用来操作前序表达式树的类
 *   
 * 创建时间: 2009-11-2 23:34:40
 *============================================*/
using System;
using System.Collections.Generic;

using System.Text;
using System.Collections;

namespace 命题证明
{
    /// <summary>
    /// 表达式，现在用的是后序表达式
    /// </summary> 
    class Expression : IEquatable<Expression>
    {
        //这个构造函数做得有点绝，只能接受中序形式的表达式，这样也比较省事，对外接口多了后，虽然方便了，不过也容易出错了
        /// <summary>表达式构造函数，接受中序表达式</summary>
        /// <param name="expression">中序表达式</param>
        public Expression( string expression )
        {
            string t = expression.Replace( " ", "" ).ToLower();
            ValidateExpression.CheckValidate( t );
            //if ( p != null )
            //{
            //    throw new Exception( p.Message );
            //}
            MiddleExpression = t;
            AfterExpress = ExpressionFactory.MiddleToAfter( t );
            head = ConvertToTree( AfterExpress );
        }

        #region "属性区"
        /// <summary>自然表达式</summary>
        public string MiddleExpression { get; set; }

        /// <summary>后序形式</summary>
        public string AfterExpress { get; set; }

        List<WordNode> wordNodes = new List<WordNode>();
        List<char> words = new List<char>();
        //下面二个属性都应该有
        /// <summary>表达式中所有的运算字母的节点，这个节点是个指针，指向树中的字母节点</summary> 
        public List<WordNode> WordNodes
        {
            get { return wordNodes; }
        }
        /// <summary>与上面不同的是，这个属性对字母只存储一次，比如(a∨b)∧┐b中，这个属性只存储a,b</summary>
        public List<char> Words
        {
            get { return words; }
        }


        //这了实现替换，所以要用Node类来存储
        List<Node> operatorNodes = new List<Node>();

        /// <summary>这个表达式中所有的操作符节点，添加这个属性，主要是为了整个替代的要求</summary>
        public List<Node> OperatorNodes
        {
            get { return operatorNodes; }
            set { operatorNodes = value; }
        }

        Node head = new Node();
        /// <summary>表达式树的头节点</summary>
        public Node Head
        {
            get { return head; }
            set { head = value; }
        }

        //这里可用继承，将这个属性放在子类中。
        //List<MiddleParameter> middleResults = new List<MiddleParameter>();
        ///// <summary>在计算真值表时的中间步骤</summary>
        //public List<MiddleParameter> MiddleResults
        //{
        //    get { return middleResults; }
        //    set { middleResults = value; }
        //}

        #endregion



        //因为下面两个转换和这个类有很大的关系，所以就没有将其分离出去，但是现在却要在这个类的外面将后序表达式转化成出来了，这样就必须让这个份代码出现两次了
        /// <summary>将后序表达式转换成树形结构</summary> 
        Node ConvertToTree( string afterExpression )
        {
            wordNodes.Clear();
            Stack<Node> tree = new Stack<Node>();
            for ( int i = 0; i < afterExpression.Length; i++ )
            {
                char ch = afterExpression[i];
                //不是操作符
                if ( !MainChar.IsOperator( ch ) )
                {
                    //是字母
                    if ( !MainChar.IsConst( ch ) )
                    {
                        if ( !words.Exists( delegate( char value ) {
                            if ( ch == value )
                                return true;
                            return false;
                        } ) )
                            words.Add( ch );
                        WordNode t = new WordNode( ch );
                        wordNodes.Add( t );
                        tree.Push( t );
                    }
                    //是常数0  1 
                    else
                    {
                        tree.Push( new ConstNode( ExpressionFactory.Convert( ch ) ) );
                    }
                }
                //操作符
                else if ( MainChar.IsOperator( ch ) )
                {
                    Node right = tree.Pop();
                    Node left = null;
                    //非操作符的左节点为空
                    if ( ch != MainChar.Not )
                    {
                        left = tree.Pop();
                    }
                    OperatorNode t = new OperatorNode( left, right, (Operator)ch );
                    if ( left != null )
                    {
                        left.Parent = t;
                    }
                    right.Parent = t;
                    tree.Push( t );
                    operatorNodes.Add( t );
                }
            }
            return tree.Pop();
        }

        /// <summary>将树形转化为中序字符串</summary>
        /// <returns>中序字符串</returns>    
        string ConvertToMiddle( Node node )
        {
            string result = "";
            if ( node is ConstNode )
            {
                //if ( !node.IsTrue )
                //    result += "┐"; 这样死亡的代码值得纪念
                result += ExpressionFactory.Convert( ( node as ConstNode ).Value );
            }
            else if ( node is WordNode )
            {
                result += ( node as WordNode ).Word.ToString();
            }
            else if ( node is OperatorNode )
            {
                if ( node != head )
                    result += "(";
                result += ConvertToMiddle( node.Left );
                result += ( (char)( node as OperatorNode ).Operator ).ToString();
                result += ConvertToMiddle( node.Right );
                if ( node != head )
                {
                    result += ")";
                }
            }
            return result;
        }

        /// <summary>求此表达式的逻辑真假值</summary>
        /// <param name="values">这个参数依次给字母赋真假值</param>
        /// <returns>给参数赋值后，整个表示式的真假值</returns>
        public bool CalValue( List<bool> values )
        {
            for ( int i = 0; i < values.Count; i++ )
            {
                //先对字母进行赋值
                //WordNodes[i].Value = values[i];
                wordNodes.ForEach( delegate( WordNode w ) {
                    if ( w.Word == words[i] )
                        w.Value = values[i];
                } );
            }
            //middleResults.Clear();
            return CalValue( head );
        }

        bool CalValue( Node node )
        {
            //字母
            if ( node is WordNode )
            {
                //return (note as OperandNode).Value && note.IsTrue; // 这里很有迷惑性，不能用 && 或要用^  ,通过下面的真值表就可以看出来
                /*     p ┐
                        0   0     0
                 *     0   1      1
                 *     1   0      1
                 *     1   1      0
                 */
                return ( node as WordNode ).Value;
            }
            //常数
            else if ( node is ConstNode )
            {
                return ( node as ConstNode ).Value;
            }
            //操作符
            else
            {
                //为了在求真值有时，体现出中间过程，所以在这里要将中间结果存留下来
                bool result;
                bool leftResult = false;
                if ( node.Left != null )
                {
                    leftResult = CalValue( node.Left );
                }
                result = MainChar.CalChar( ( node as OperatorNode ).Operator, leftResult, CalValue( node.Right ) );
                //middleResults.Add( new MiddleParameter( node, result ) );
                return result;
            }
        }

        /// <summary>比较表达式是否一样，析取、合取满足交换律</summary> 
        public bool Equals( Expression other )
        {
            if ( this.Words.Count != other.Words.Count )
                return false;
            //两个树的字母对应的映射关系，这里是为了考虑字母顺序不一样的情况
            //a  b  c 对应到 c  a  b,就是 1 2 0
            //TODO:这里有改动
            List<int> Correspond = new List<int>();
            int find = -1;
            foreach ( char node in Words )
            {
                find = -1;
                find = other.Words.FindIndex( delegate( char c ) {
                    if ( node == c )
                        return true;
                    return false;
                } );
                if ( find != -1 )
                {
                    Correspond.Add( find );
                }
            }
            if ( Correspond.Count != Words.Count )
                return false;

            TableWork table1 = new TableWork( this );
            TableWork table2 = new TableWork( other );
            for ( int i = 0; i < table1.Records.Count; i++ )
            {
                //List<bool> bin = new List<bool>() { false , false , false };
                bool[] bin = new bool[Correspond.Count];
                for ( int j = 0; j < Correspond.Count; j++ )
                {
                    bin[Correspond[j]] = table1.Records[i].Binary[j];
                }
                OneRecord one = table2.Records.Find( delegate( OneRecord o ) {
                    if ( o.Binary.Equals( new List<bool>( bin ) ) )
                        return true;
                    return false;
                } );
                if ( one.Value != table1.Records[i].Value )
                    return false;
            }

            return true;
        }

        /// <summary>返回这个表达式的中序形式，并且在最外面有括号</summary>
        public override string ToString()
        {
            return "(" + ConvertToMiddle( head ) + ")";
        }
        /// <summary>"A"返回后序形式，"M"返回中序形式</summary>
        internal string ToString( string p )
        {
            if ( p == "A" )
            {
                return ExpressionFactory.ConvertToAfter( head );
            }
            else if ( p == "M" )
            {
                return ToString();
            }
            throw new Exception( "未定义符号" );
        }

        /// <summary>将此对象复制一份，复制后的对象于此对象没有内存上的关系</summary> 
        public Expression Clone()
        {
            return new Expression( this.ToString() );
        }

        /// <summary>这个表达式是否包含参数中的表达式</summary>
        internal bool Contain( Expression value )
        {
            if ( value.Words.Count > this.Words.Count )
                return false;
            if ( value.WordNodes.Count > this.WordNodes.Count )
                return false;
            foreach ( char c in value.Words )
            {
                //int countThis = this.WordNodes ( delegate( WordNode w ) {
                //    if ( w.Word == c )
                //        return true;
                //    return false;
                //} );
                int countThis = NodeCount( this.WordNodes, c );
                //int countValue = value.WordNodes.Count( delegate( WordNode w ) {
                //    if ( w.Word == c )
                //        return true;
                //    return false;
                //} );
                int countValue = NodeCount( value.WordNodes, c );
                if ( countValue > countThis )
                    return false;
            }

            return true;
        }
        int NodeCount( List<WordNode> nodes, char c )
        {
            int count = 0;
            foreach ( WordNode w in nodes )
            {
                if ( w.Word == c )
                    count++;
            }
            return count;
        }

    }
}

//又是一串死亡了的代码，现在自己定义了两个关于表达式的概念：全等、相似
//全等就是完成相等，可以相互恒等变形。
//相似就是将节点整个替换后结构相同
//判断两棵表达式树是否相等，现在有了真值表，在比较两树是否相等时，就可用真值表了
//public bool Equals( Expression other )
//{
//    TableWork t1 = new TableWork( this );
//    TableWork t2 = new TableWork( other );
//    if ( Head is ConstNode && other.Head is ConstNode )
//    {
//        return !( CalValue( Head ) ^ CalValue( other.Head ) );
//    }
//    if ( this.Head is ConstNode )
//    {
//        if ( CalValue( head ) )
//        {
//            foreach ( OneRecord o in t2.Records )
//            {
//                if ( !o.Value )
//                    return false;
//            }
//            return true;
//        }
//        else
//        {
//            foreach ( OneRecord o in t2.Records )
//            {
//                if ( o.Value )
//                    return false;
//            }
//            return true;
//        }
//    }// end if this.Head is ConstNode
//    else if ( other.Head is ConstNode )
//    {
//        if ( CalValue( other.head ) )
//        {
//            foreach ( OneRecord o in t1.Records )
//            {
//                if ( !o.Value )
//                    return false;
//            }
//            return true;
//        }
//        else
//        {
//            foreach ( OneRecord o in t1.Records )
//            {
//                if ( o.Value )
//                    return false;
//            }
//            return true;
//        }
//    }
//    else
//    {
//        if ( this.Words.Count != other.Words.Count )
//            return false;

//        for ( int i = 0 ; i < t1.Records.Count ; i++ )
//        {
//            if ( t1.Records[i].Value != t2.Records[i].Value )
//                return false;
//        }
//        return true;
//    }
//}